确定性模拟 — World / Step / Fixed-point / SplitMix64

基于 rts-server-golang sim/ 模块解析关键词: 确定性, 固定点数学, Q16.16, SplitMix64, Desync检测, 命令执行

概述

确定性模拟是帧同步的执行层：服务端和所有客户端跑同一份代码，用同一个 seed，同一个输入，产生同一个结果。每帧执行完后计算 hash(world) 上报 HashAgg 校验。

帧同步的信任基础：只要输入相同，结果必然相同。

为什么需要确定性

破坏因素	后果
浮点精度不一致	Go 和 JS 对 `(0.1 + 0.2)` 的处理可能有微差
随机数不同步	服务端和客户端 seed/调用顺序不同，世界完全不同
迭代顺序不确定	单位处理顺序不同，先攻击谁后攻击谁就不一样

解决方案：固定点数学 + 确定性 PRNG + 排序迭代。

固定点数学 (Q16.16)

为什么不用浮点数

浮点数有三个不确定性来源：

不同 FPU 实现有微小差异
编译器可能重排浮点运算顺序（CPU 乱序）
NaN/Inf 处理不一致

固定点数用整数模拟小数，所有运算都是整数操作，结果完全一致。

Q16.16 格式

32位 int32
├─ 高16位: 整数部分（有符号）
└─ 低16位: 小数部分

示例:
Fix32(1 << 16)  = 1.00000
Fix32(1)         = 0.000015258789... (2^-16)

表示范围: -32768.0 ~ +32767.9999847
精度:     2^-16 ≈ 0.000015

核心运算

// 乘法: (a * b) >> 16
// 用 int64 中间变量防止溢出
func (a Fix32) Mul(b Fix32) Fix32 {
    return Fix32((int64(a) * int64(b)) >> Shift)
}

// 除法: (a << 16) / b
func (a Fix32) Div(b Fix32) Fix32 {
    return Fix32((int64(a) << Shift) / int64(b))
}

Vec2 定点向量

type Vec2 struct {
    X, Y Fix32
}

// 移动: 从 from 朝 target 移动 maxDist
func MoveToward(from, target Vec2, maxDist Fix32) Vec2 {
    diff := target.Sub(from)
    dSq := diff.LenSq()
    if dSq <= maxDist.Mul(maxDist) {
        return target  // 距离不足，直接到 target
    }
    d := Sqrt(dSq)
    return from.Add(diff.Scale(maxDist.Div(d)))
}

关键：比较距离用 DistSq() 而非 Dist()——避免昂贵的 Sqrt 开方运算。

Sqrt — 二分查找

func Sqrt(a Fix32) Fix32 {
    if a <= 0 { return 0 }
    n := int64(a) << Shift
    var result int64
    bit := int64(1) << 30
    for bit > 0 {
        trial := result | bit
        if trial*trial <= n {
            result = trial
        }
        bit >>= 1
    }
    return Fix32(result)
}

纯整数二分，16 次迭代固定收敛，无浮点。

SplitMix64 — 确定性 PRNG

为什么需要确定性 PRNG

// ❌ 错误：用 time.Now().UnixNano() 或 math/rand
rand.Seed(time.Now().UnixNano())  // 两边 seed 不同，结果完全不同

// ✅ 正确：所有人用同一个 seed
world := NewWorld(seed=0x12345678, ...)
rand := NewRand(seed=0x12345678)

算法

func (r *SplitMix64) Next() uint64 {
    r.state += 0x9e3779b97f4a7c15  // 黄金比例增量
    z := r.state
    z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9
    z = (z ^ (z >> 27)) * 0x94d049bb133111eb
    return z ^ (z >> 31)
}

有雪崩效应（bit 翻转影响所有输出位），输出均匀。这是 Go 标准库 math/rand 的底层实现。

确定性保证：Same seed + Same call sequence = Same output on ALL platforms

World — 游戏世界状态

type World struct {
    Tick     uint32
    Seed     uint64          // 初始 seed
    Rand     *SplitMix64     // 确定性随机
    Units    []Unit
    NextID   uint32          // 下一个单位ID
    MapSizeX Fix32           // 地图尺寸
    MapSizeY Fix32
}

Unit 结构

type Unit struct {
    ID       uint32
    Owner    uint8           // 所属玩家 0/1
    Pos      fixed.Vec2     // 当前位置
    HP       fixed.Fix32    // 当前生命
    MaxHP    fixed.Fix32    // 最大生命
    Speed    fixed.Fix32    // 移动速度(距离/tick)
    State    UnitState      // Idle/Moving/Dead
    TargetID uint32         // 攻击目标(0=none)
    MoveTo   fixed.Vec2     // 移动目的地
}

Cmd — 玩家命令

type Cmd struct {
    Player   uint8
    Op       CmdOp          // Move/Attack/Stop
    UnitID   uint32
    TargetPos fixed.Vec2    // 移动目标位置
    TargetID uint32         // 攻击目标单位
}

Step — 帧执行（3阶段）

func Step(w *World, cmds []Cmd) {
    w.Tick++

    // Phase 1: 应用命令（按 UnitID 排序）
    applyCommands(w, cmds)

    // Phase 2: 更新单位（按 UnitID 排序）
    sortUnitsByID(w)
    for i := range w.Units {
        u := &w.Units[i]
        if u.State == UnitDead { continue }
        switch u.State {
        case UnitMoving: stepMove(w, u)
        case UnitIdle:   stepAttack(w, u)
        }
    }

    // Phase 3: 移除死亡单位
    w.RemoveDead()
}

Phase 1: applyCommands

func applyCommands(w *World, cmds []Cmd) {
    for _, cmd := range cmds {
        u := w.FindUnit(cmd.UnitID)
        if u == nil || u.State == UnitDead { continue }
        if u.Owner != cmd.Player { continue }  // 合法性检查

        switch cmd.Op {
        case CmdMove:
            u.State = UnitMoving
            u.MoveTo = cmd.TargetPos
            u.TargetID = 0
        case CmdAttack:
            u.State = UnitIdle   // 将在 stepAttack 中处理
            u.TargetID = cmd.TargetID
        case CmdStop:
            u.State = UnitIdle
            u.TargetID = 0
        }
    }
}

Phase 2: stepMove

func stepMove(w *World, u *Unit) {
    u.Pos = fixed.MoveToward(u.Pos, u.MoveTo, u.Speed)
    u.Pos.X = u.Pos.X.Clamp(0, w.MapSizeX)  // 边界限制
    u.Pos.Y = u.Pos.Y.Clamp(0, w.MapSizeY)
    if u.Pos.DistSq(u.MoveTo) <= fixed.Eps { // 到达目的地
        u.State = UnitIdle
    }
}

Phase 2: stepAttack

func stepAttack(w *World, u *Unit) {
    if u.TargetID == 0 { return }
    target := w.FindUnit(u.TargetID)
    if target == nil || target.State == UnitDead {
        u.TargetID = 0
        return
    }

    distSq := u.Pos.DistSq(target.Pos)
    rangeSq := AttackRange.Mul(AttackRange)  // 2² = 4

    if distSq <= rangeSq {
        // 在攻击范围内：造成伤害
        target.HP = target.HP.Sub(AttackDamage)  // 0.5/tick
        if target.HP <= 0 {
            target.State = UnitDead
            target.HP = 0
        }
    } else {
        // 不在攻击范围：朝目标移动
        u.Pos = fixed.MoveToward(u.Pos, target.Pos, u.Speed)
    }
}

三个确定性保证

保证	实现
固定点数学	所有位置/速度/伤害都是 `Fix32`（int32），乘法用移位，无 float
确定性 PRNG	`SplitMix64`，同 seed 同序列，全平台一致
排序迭代	`sortUnitsByID()` 后处理，单位按 ID 从小到大

World Hash — Desync 签名

func Hash(w *World) uint64 {
    var h uint64 = 14695981039346656037  // FNV offset basis

    h = fnvMix(h, littleEndian(w.Tick))
    h = fnvMix(h, littleEndian(uint32(len(w.Units))))

    for i := range w.Units {  // 已按 ID 排序
        h = hashUnit(h, &w.Units[i])
    }
    return h
}

func hashUnit(h uint64, u *Unit) uint64 {
    // 固定 22 字节布局，无歧义
    // ID(4) + Owner(1) + State(1) + HP(4) + PosX(4) + PosY(4) + TargetID(4)
    var buf [22]byte
    binary.LittleEndian.PutUint32(buf[0:4], u.ID)
    buf[4] = u.Owner
    buf[5] = uint8(u.State)
    binary.LittleEndian.PutUint32(buf[6:10], uint32(u.HP.Raw()))
    binary.LittleEndian.PutUint32(buf[10:14], uint32(u.Pos.X.Raw()))
    binary.LittleEndian.PutUint32(buf[14:18], uint32(u.Pos.Y.Raw()))
    binary.LittleEndian.PutUint32(buf[18:22], u.TargetID)
    return fnvMix(h, buf[:])
}

两端 World 状态相同时 hash 必然相同。

Pitaya

确定性模拟 — World / Step / Fixed-point / SplitMix64

概述

为什么需要确定性

固定点数学 (Q16.16)

为什么不用浮点数

Q16.16 格式

核心运算

Vec2 定点向量

Sqrt — 二分查找

SplitMix64 — 确定性 PRNG

为什么需要确定性 PRNG

算法

World — 游戏世界状态

Unit 结构

Cmd — 玩家命令

Step — 帧执行（3阶段）

Phase 1: applyCommands

Phase 2: stepMove

Phase 2: stepAttack

三个确定性保证

World Hash — Desync 签名

相关

Pitaya

确定性模拟 — World / Step / Fixed-point / SplitMix64 ​

概述 ​

为什么需要确定性 ​

固定点数学 (Q16.16) ​

为什么不用浮点数 ​

Q16.16 格式 ​

核心运算 ​

Vec2 定点向量 ​

Sqrt — 二分查找 ​

SplitMix64 — 确定性 PRNG ​

为什么需要确定性 PRNG ​

算法 ​

World — 游戏世界状态 ​

Unit 结构 ​

Cmd — 玩家命令 ​

Step — 帧执行（3阶段） ​

Phase 1: applyCommands ​

Phase 2: stepMove ​

Phase 2: stepAttack ​

三个确定性保证 ​

World Hash — Desync 签名 ​

相关 ​

确定性模拟 — World / Step / Fixed-point / SplitMix64

概述

为什么需要确定性

固定点数学 (Q16.16)

为什么不用浮点数

Q16.16 格式

核心运算

Vec2 定点向量

Sqrt — 二分查找

SplitMix64 — 确定性 PRNG

为什么需要确定性 PRNG

算法

World — 游戏世界状态

Unit 结构

Cmd — 玩家命令

Step — 帧执行（3阶段）

Phase 1: applyCommands

Phase 2: stepMove

Phase 2: stepAttack

三个确定性保证

World Hash — Desync 签名

相关